package FloodFill;

import java.util.LinkedList;
import java.util.Queue;

public class SurroundedRegions {
    // 辅助向量数组
    int[] dx = { 1, -1, 0, 0 };
    int[] dy = { 0, 0, -1, 1 };

    int m; // 对应 x 的坐标
    int n; // 对应 y 的坐标

    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;

        // 1.处理边缘情况的连通块, 把 `O` 修改成 `?`(首行和尾行)
        for (int y = 0; y < n; y++) {
            if (board[0][y] == 'O') {
                bfs(board, 0, y);
            }
            if (board[m - 1][y] == 'O') {
                bfs(board, m - 1, y);
            }
        }

        // 处理首列和尾列
        for (int x = 0; x < m; x++) {
            if (board[x][0] == 'O') {
                bfs(board, x, 0);
            }
            if (board[x][n - 1] == 'O') {
                bfs(board, x, n - 1);
            }
        }


        // 2.遍历整个矩阵,把内部的 `O` 全部修改成 `X`, 然后把 `?` 修改成 `O`
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '?') {
                    board[i][j] = 'O';
                }
            }
        }

    }

    // bfs: 把边缘连通块的 `O` 全部改成其他字符 `?`
    public void bfs(char[][] board, int OOy, int OOx) {
        // 用队列存储当前原点
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] { OOx, OOy });
        // 当前点符合修改成 `?`
        board[OOx][OOy] = '?';

        while (!queue.isEmpty()) {
            // 取出上一层点
            int[] point = queue.poll();
            // 分解点坐标
            int Ox = point[0];
            int Oy = point[1];

            // 遍历下一层节点, offer符合要求的点
            for (int i = 0; i < 4; i++) {
                int x = Ox + dx[i];
                int y = Oy + dy[i];

                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
                    queue.offer(new int[] { x, y });
                    board[x][y] = '?';
                }
            }
        }
    }
}
